package pers.qianyu.month_202102.date_20210222;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 面试题 04.05. 合法二叉搜索树
 * https://leetcode-cn.com/problems/legal-binary-search-tree-lcci/
 *
 * @author mizzle rain
 * @date 2021-02-22 12:57
 */
public class IsValidBST {
    // 通过中序遍历实现
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode p = root;
        int pre = Integer.MIN_VALUE, flag = 0;
        while (p != null || !st.isEmpty()) {
            while (p != null) {
                st.addLast(p);
                p = p.left;
            }
            TreeNode node = st.pollLast();
            if (flag == 1 && node.val <= pre) return false;
            flag = 1;
            pre = node.val;
            p = node.right;
        }
        return true;
    }

    // 通过递归实现
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;
        return recur(root, null, null);
    }

    private boolean recur(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) return true;
        if (max != null && root.val >= max.val) return false;
        if (min != null && root.val <= min.val) return false;
        return recur(root.left, min, root) && recur(root.right, root, max);
    }
}
